/*-------------------------------------------------------------------------
 *
 * logtape.c
 *	  管理临时文件中的“逻辑带”。
 *
 * 此模块的存在是为了支持通过多次合并传递进行排序（见
 * tuplesort.c）。合并是磁带设备的理想算法，但是如果
 * 我们通过为每个“磁带”创建一个单独的文件在磁盘上实现它，
 * 那会有一个烦人的问题：峰值空间使用量至少是要排序的数据
 * 音量的两倍。（这是因为每个数据将出现在最后
 * 合并传递的输入和输出磁带中。）
 *
 * 我们可以通过识别任何一个磁带的数据集来解决此问题
 * （最后输出的可能除外）是以完全顺序的方式写入和读取一次。
 * 因此，一旦读取的数据将不再需要，我们可以回收其
 * 空间以供生成的新磁带数据集使用。通过这种方式，
 * 总空间使用实际上只是实际数据量，加上微不足道的
 * 记账和启动/停止开销。
 *
 * 很少有操作系统允许随意地将文件的部分释放回操作系统，
 * 因此，我们必须在单个逻辑文件内自行实现这种空间回收。
 * logtape.c 存在的目的是执行这项记账工作，并向tuplesort.c提供
 * N个独立磁带设备的假象。请注意，logtape.c本身依赖于
 * buffile.c提供大于底层操作系统可能支持的“逻辑文件”。
 *
 * 为了简单起见，我们在底层文件中以BLCKSZ大小的块分配和释放空间。
 * 空间分配归结为跟踪底层文件中哪些块属于哪个逻辑磁带，
 * 以及任何空闲块（已回收但尚未重用）。
 * 每个逻辑磁带中的块形成一条链，每个块中都有prev和next指针。
 *
 * 初始写入过程保证以完全顺序的方式填充底层文件，
 * 无论数据是如何在逻辑磁带中被分配的。
 * 一旦我们开始合并传递，访问模式就会变得明显不可预测——但
 * 涉及的寻道操作应与将每个逻辑磁带保存在单独文件中的情况相当，
 * 因此没有严重的性能损失用于获得回收的空间节省。
 * 我们尝试通过在有选择的时候总是写入最低编号的空闲块来
 * 局部化写入访问；尚不清楚这是否有帮助，但也无妨。（XXX或许空闲块的LIFO策略会更好？）
 *
 * 为了进一步使输入/输出更加顺序，我们可以在读取时使用更大的
 * 缓冲区，并在缓冲区变得空时，一次性从同一磁带中读取多个块。
 *
 * 为了支持向最低空闲块写入的上述策略，空闲列表是一个最小堆。
 *
 * 由于所有的记账和缓冲区内存都是用palloc()分配的，
 * 并且底层文件是用OpenTemporaryFile创建的，因此即使通过
 * ereport(ERROR)中止处理，逻辑磁带集的所有资源也必定会被
 * 清理。为了避免混淆，调用者应确保对单个LogicalTapeSet的
 * 所有调用在同一palloc上下文中进行。
 *
 * 为了支持涉及多个工作者对tuplesort.c例程的协调调用的并行排序操作，
 * 有必要将每个工作者的BufFile/tapeset连接成一个由领导者管理的单个逻辑带。
 * 当发生这种情况时，工作者应生成一个最终的物化磁带（他们的整个输出）。
 * 输入磁带的数量总是与参与者（工作者Tuplesortstates）的数量相同。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, 加利福尼亚大学董事会
 *
 * IDENTIFICATION
 *	  src/backend/utils/sort/logtape.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include <fcntl.h>

#include "storage/buffile.h"
#include "utils/builtins.h"
#include "utils/logtape.h"
#include "utils/memdebug.h"
#include "utils/memutils.h"

/*
 * 每个 BLCKSZ 块的末尾存储一个 TapeBlockTrailer。
 *
 * 一卷磁带的第一个块的 prev == -1。卷磁带的最后一个块
 * 在 'next' 中存储该块的有效字节数的反转，
 * 因此 next < 0 表示最后一个块。
 */
typedef struct TapeBlockTrailer
{
	long		prev;			/* 此磁带上的前一个块，或在第一个块时为 -1 */
	long		next;			/* 此磁带上的下一个块，或最后一个块的有效字节数（如果 < 0） */
} TapeBlockTrailer;

#define TapeBlockPayloadSize  (BLCKSZ - sizeof(TapeBlockTrailer))
#define TapeBlockGetTrailer(buf) \
	((TapeBlockTrailer *) ((char *) buf + TapeBlockPayloadSize))

#define TapeBlockIsLast(buf) (TapeBlockGetTrailer(buf)->next < 0)
#define TapeBlockGetNBytes(buf) \
	(TapeBlockIsLast(buf) ? \
	 (- TapeBlockGetTrailer(buf)->next) : TapeBlockPayloadSize)
#define TapeBlockSetNBytes(buf, nbytes) \
	(TapeBlockGetTrailer(buf)->next = -(nbytes))

/*
 * 当多个磁带同时被写入时（如在 HashAgg 中），
 * 通过预分配块号给单独的磁带以避免过度碎片化。
 * 每个预分配块从 TAPE_WRITE_PREALLOC_MIN 块开始，
 * 增加到 TAPE_WRITE_PREALLOC_MAX 块。
 *
 * 预分配不执行任何文件系统操作；仅仅是保留块号。
 * 这可能导致稀疏写入，进而导致 ltsWriteBlock() 用零填补空洞。
 */
#define TAPE_WRITE_PREALLOC_MIN 8
#define TAPE_WRITE_PREALLOC_MAX 128

/*
 * 此数据结构表示存储在同一文件中的一组"逻辑磁带"中的单个
 * "逻辑磁带"。
 *
 * 在写入时，我们将当前部分写入的数据块保存在缓冲区中。
 * 在读取时，我们可以在缓冲区中保留多个块。请注意，
 * 我们在将块读入缓冲区时不会保留块的尾部。因此，
 * 缓冲区包含来自磁带的一大块连续数据。
 */
struct LogicalTape
{
	LogicalTapeSet *tapeSet;	/* 该磁带所在的磁带集 */

	bool		writing;		/* 在写入阶段的 T */
	bool		frozen;			/* 如果块在读取时不应该被释放，则为 T */
	bool		dirty;			/* 缓冲区是否需要写入？ */

	/*
	 * 磁带的第一个、当前和下一个块的块号。
	 *
	 * “当前”块号在写入或从冻结的磁带读取时才有效。
	 * （从未冻结的磁带读取时，我们使用一个较大的
	 * 读取缓冲区来保存多个块，因此“当前”块是
	 * 模糊的。）
	 *
	 * 当对工作磁带 BufFiles 进行连接时，在读取时将偏移
	 * 应用于统一 BufFile 空间的第一个块。
	 */
	long		firstBlockNumber;
	long		curBlockNumber;
	long		nextBlockNumber;
	long		offsetBlockNumber;

	/*
	 * 当前数据块的缓冲区。
	 */
	char	   *buffer;			/* 物理缓冲区（单独 palloc'） */
	int			buffer_size;	/* 缓冲区的分配大小 */
	int			max_size;		/* 最高有效、安全的 buffer_size */
	int			pos;			/* 缓冲区中下一个读取/写入位置 */
	int			nbytes;			/* 缓冲区中有效字节的总数 */

	/*
	 * 预分配的块号保存在按降序排列的数组中；
	 * 从数组末尾消耗块（最低块号优先）。
	 */
	long	   *prealloc;
	int			nprealloc;		/* 列表中元素的数量 */
	int			prealloc_size;	/* 列表可以容纳的元素数量 */
};

/*
 * 此数据结构表示一组相关的“逻辑磁带”，
 * 共享单个基础文件中的空间。
 * （但是，“文件”如果需要逃避操作系统对文件大小的限制，
 * 可能是多个文件；buffile.c 为我们处理这个问题。）
 * 属于磁带集的磁带可以按需动态创建和销毁。
 */
struct LogicalTapeSet
{
	BufFile    *pfile;			/* 整个磁带集的基础文件 */
	SharedFileSet *fileset;
	int			worker;			/* 如果共享则为工作号，领头/串行时为 -1 */

	/*
	 * 文件大小跟踪。nBlocksWritten 是基础文件的大小，
	 * 以 BLCKSZ 块为单位。nBlocksAllocated 是由 ltsReleaseBlock() 
	 * 分配的块数，它总是大于或等于 nBlocksWritten。nBlocksAllocated
	 * 和 nBlocksWritten 之间的块是已为磁带分配但尚未写入
	 * 基础文件的块。nHoleBlocks 跟踪工作空间间未使用空洞的总块数，
	 * 这些空洞是在 BufFile 连接后产生的。
	 */
	long		nBlocksAllocated;	/* 分配的块数 */
	long		nBlocksWritten; /* 基础文件中使用的块数 */
	long		nHoleBlocks;	/* 剩余的“空洞”块数 */

	/*
	 * 我们在 freeBlocks[] 中存储回收和可用块的数量。
	 * 当没有这样的块时，我们会扩展基础文件。
	 *
	 * 如果 forgetFreeSpace 为真，则任何释放的块仅被遗忘，
	 * 而不是记住在 freeBlocks[] 中。有关详细说明，请参见 
	 * LogicalTapeSetForgetFreeSpace() 的注释。
	 */
	bool		forgetFreeSpace;	/* 我们是否记住了空闲块？ */
	long	   *freeBlocks;		/* 可变大小数组，存放最小堆 */
	long		nFreeBlocks;	/* 当前空闲块数 */
	Size		freeBlocksLen;	/* freeBlocks[] 当前分配的长度 */
	bool		enable_prealloc;	/* 是否预分配写入块？ */
};

static LogicalTape *fc_ltsCreateTape(LogicalTapeSet *fc_lts);
static void fc_ltsWriteBlock(LogicalTapeSet *fc_lts, long fc_blocknum, void *fc_buffer);
static void fc_ltsReadBlock(LogicalTapeSet *fc_lts, long fc_blocknum, void *fc_buffer);
static long fc_ltsGetBlock(LogicalTapeSet *fc_lts, LogicalTape *fc_lt);
static long fc_ltsGetFreeBlock(LogicalTapeSet *fc_lts);
static long fc_ltsGetPreallocBlock(LogicalTapeSet *fc_lts, LogicalTape *fc_lt);
static void fc_ltsReleaseBlock(LogicalTapeSet *fc_lts, long fc_blocknum);
static void fc_ltsInitReadBuffer(LogicalTape *fc_lt);


/*
 * 将块大小的缓冲区写入基础文件的指定块。
 *
 * 不需要错误返回约定；我们会在任何错误时使用 ereport()。
 */
static void fc_ltsWriteBlock(LogicalTapeSet *fc_lts, long fc_blocknum, void *fc_buffer)
{
	/*
	 * BufFile 不支持“空洞”，因此如果我们即将写入一个
	 * 超过当前文件末尾的块，将当前文件末尾和目标块之间的
	 * 空间填充为零。
	 *
	 * 这可能发生在磁带预分配块时；或者对于可能尚未刷新
	 * 的磁带的最后一个块。
	 *
	 * 请注意，BufFile 连接可能会在工作者拥有的块范围之间留
	 * 下“空洞”。这些仅用于报告目的进行跟踪。我们绝不会
	 * 从这些空洞块中读取或写入，因此这里不予考虑。
	 */
	while (fc_blocknum > fc_lts->nBlocksWritten)
	{
		PGAlignedBlock fc_zerobuf;

		MemSet(fc_zerobuf.data, 0, sizeof(fc_zerobuf));

		fc_ltsWriteBlock(fc_lts, fc_lts->nBlocksWritten, fc_zerobuf.data);
	}

	/* 写入请求的块 */
	if (BufFileSeekBlock(fc_lts->pfile, fc_blocknum) != 0)
		ereport(ERROR,
				(errcode_for_file_access(),
				 errmsg("could not seek to block %ld of temporary file",
						fc_blocknum)));
	BufFileWrite(fc_lts->pfile, fc_buffer, BLCKSZ);

	/* 如果扩展了文件，则更新 nBlocksWritten */
	if (fc_blocknum == fc_lts->nBlocksWritten)
		fc_lts->nBlocksWritten++;
}

/*
 * 从基础文件的指定块读取块大小的缓冲区。
 *
 * 不需要错误返回约定；我们会在任何错误时使用 ereport()。
 * 此模块绝不应尝试读取它不知道存在的块。
 */
static void fc_ltsReadBlock(LogicalTapeSet *fc_lts, long fc_blocknum, void *fc_buffer)
{
	size_t		fc_nread;

	if (BufFileSeekBlock(fc_lts->pfile, fc_blocknum) != 0)
		ereport(ERROR,
				(errcode_for_file_access(),
				 errmsg("could not seek to block %ld of temporary file",
						fc_blocknum)));
	fc_nread = BufFileRead(fc_lts->pfile, fc_buffer, BLCKSZ);
	if (fc_nread != BLCKSZ)
		ereport(ERROR,
				(errcode_for_file_access(),
				 errmsg("could not read block %ld of temporary file: read only %zu of %zu bytes",
						fc_blocknum, fc_nread, (size_t) BLCKSZ)));
}

/*
 * 尽可能多地读取块到每个磁带缓冲区中。
 *
 * 如果读取了任何内容则返回 true，EOF 时返回 'false'。
 */
static bool fc_ltsReadFillBuffer(LogicalTape *fc_lt)
{
	fc_lt->pos = 0;
	fc_lt->nbytes = 0;

	do
	{
		char	   *fc_thisbuf = fc_lt->buffer + fc_lt->nbytes;
		long		fc_datablocknum = fc_lt->nextBlockNumber;

		/* 获取下一个块编号 */
		if (fc_datablocknum == -1L)
			break;				/* EOF */
		/* 应用工作者偏移量，领导磁带集需要 */
		fc_datablocknum += fc_lt->offsetBlockNumber;

		/* 读取块 */
		fc_ltsReadBlock(fc_lt->tapeSet, fc_datablocknum, (void *) fc_thisbuf);
		if (!fc_lt->frozen)
			fc_ltsReleaseBlock(fc_lt->tapeSet, fc_datablocknum);
		fc_lt->curBlockNumber = fc_lt->nextBlockNumber;

		fc_lt->nbytes += TapeBlockGetNBytes(fc_thisbuf);
		if (TapeBlockIsLast(fc_thisbuf))
		{
			fc_lt->nextBlockNumber = -1L;
			/* EOF */
			break;
		}
		else
			fc_lt->nextBlockNumber = TapeBlockGetTrailer(fc_thisbuf)->next;

		/* 如果缓冲区还有空间，则提前到下一个块 */
	} while (fc_lt->buffer_size - fc_lt->nbytes > BLCKSZ);

	return (fc_lt->nbytes > 0);
}

static inline unsigned long fc_left_offset(unsigned long fc_i)
{
	return 2 * fc_i + 1;
}

static inline unsigned long fc_right_offset(unsigned long fc_i)
{
	return 2 * fc_i + 2;
}

static inline unsigned long fc_parent_offset(unsigned long fc_i)
{
	return (fc_i - 1) / 2;
}

/*
 * 获取下一个要写入的块。
 */
static long fc_ltsGetBlock(LogicalTapeSet *fc_lts, LogicalTape *fc_lt)
{
	if (fc_lts->enable_prealloc)
		return fc_ltsGetPreallocBlock(fc_lts, fc_lt);
	else
		return fc_ltsGetFreeBlock(fc_lts);
}

/*
 * 从磁带集的全局空闲列表最小堆中选择当前未使用的
 * 最低块。
 */
static long fc_ltsGetFreeBlock(LogicalTapeSet *fc_lts)
{
	long	   *fc_heap = fc_lts->freeBlocks;
	long		fc_blocknum;
	long		fc_heapsize;
	long		fc_holeval;
	unsigned long fc_holepos;

	/* 空闲列表为空；分配一个新块 */
	if (fc_lts->nFreeBlocks == 0)
		return fc_lts->nBlocksAllocated++;

	/* 如果堆包含一个元素，则很简单 */
	if (fc_lts->nFreeBlocks == 1)
	{
		fc_lts->nFreeBlocks--;
		return fc_lts->freeBlocks[0];
	}

	/* 移除最小堆的顶部 */
	fc_blocknum = fc_heap[0];

	/* 我们将用最小堆数组的末尾替换它 */
	fc_holeval = fc_heap[--fc_lts->nFreeBlocks];

	/* 向下筛选 */
	fc_holepos = 0;				/* holepos 是 "hole" 的位置 */
	fc_heapsize = fc_lts->nFreeBlocks;
	while (true)
	{
		unsigned long fc_left = fc_left_offset(fc_holepos);
		unsigned long fc_right = fc_right_offset(fc_holepos);
		unsigned long fc_min_child;

		if (fc_left < fc_heapsize && fc_right < fc_heapsize)
			fc_min_child = (fc_heap[fc_left] < fc_heap[fc_right]) ? fc_left : fc_right;
		else if (fc_left < fc_heapsize)
			fc_min_child = fc_left;
		else if (fc_right < fc_heapsize)
			fc_min_child = fc_right;
		else
			break;

		if (fc_heap[fc_min_child] >= fc_holeval)
			break;

		fc_heap[fc_holepos] = fc_heap[fc_min_child];
		fc_holepos = fc_min_child;
	}
	fc_heap[fc_holepos] = fc_holeval;

	return fc_blocknum;
}

/*
 * 返回磁带预分配列表中的最低空闲块编号。
 * 如果需要，从磁带集的空闲列表中重新填充预分配列表。
 */
static long fc_ltsGetPreallocBlock(LogicalTapeSet *fc_lts, LogicalTape *fc_lt)
{
	/* 按降序排列，因此返回最后一个元素 */
	if (fc_lt->nprealloc > 0)
		return fc_lt->prealloc[--fc_lt->nprealloc];

	if (fc_lt->prealloc == NULL)
	{
		fc_lt->prealloc_size = TAPE_WRITE_PREALLOC_MIN;
		fc_lt->prealloc = (long *) palloc(sizeof(long) * fc_lt->prealloc_size);
	}
	else if (fc_lt->prealloc_size < TAPE_WRITE_PREALLOC_MAX)
	{
		/* 当预分配列表耗尽时，扩大大小 */
		fc_lt->prealloc_size *= 2;
		if (fc_lt->prealloc_size > TAPE_WRITE_PREALLOC_MAX)
			fc_lt->prealloc_size = TAPE_WRITE_PREALLOC_MAX;
		fc_lt->prealloc = (long *) repalloc(fc_lt->prealloc,
										 sizeof(long) * fc_lt->prealloc_size);
	}

	/* 重新填充预分配列表 */
	fc_lt->nprealloc = fc_lt->prealloc_size;
	for (int fc_i = fc_lt->nprealloc; fc_i > 0; fc_i--)
	{
		fc_lt->prealloc[fc_i - 1] = fc_ltsGetFreeBlock(fc_lts);

		/* 验证降序 */
		Assert(fc_i == fc_lt->nprealloc || fc_lt->prealloc[fc_i - 1] > fc_lt->prealloc[fc_i]);
	}

	return fc_lt->prealloc[--fc_lt->nprealloc];
}

/*
 * 将块编号返回到空闲列表。
 */
static void fc_ltsReleaseBlock(LogicalTapeSet *fc_lts, long fc_blocknum)
{
	long	   *fc_heap;
	unsigned long fc_holepos;

	/*
	 * 如果我们不再关心记住空闲空间，则不执行任何操作。
	 */
	if (fc_lts->forgetFreeSpace)
		return;

	/*
	 * 如果满了，则扩大 freeBlocks 数组。
	 */
	if (fc_lts->nFreeBlocks >= fc_lts->freeBlocksLen)
	{
		/*
		 * 如果自由列表变得非常大，只需返回并泄漏这个空闲
		 * 块。
		 */
		if (fc_lts->freeBlocksLen * 2 * sizeof(long) > MaxAllocSize)
			return;

		fc_lts->freeBlocksLen *= 2;
		fc_lts->freeBlocks = (long *) repalloc(fc_lts->freeBlocks,
											fc_lts->freeBlocksLen * sizeof(long));
	}

	/* 在 minheap 数组末尾创建一个 "hole" */
	fc_heap = fc_lts->freeBlocks;
	fc_holepos = fc_lts->nFreeBlocks;
	fc_lts->nFreeBlocks++;

	/* 向上过滤以插入 blocknum */
	while (fc_holepos != 0)
	{
		unsigned long fc_parent = fc_parent_offset(fc_holepos);

		if (fc_heap[fc_parent] < fc_blocknum)
			break;

		fc_heap[fc_holepos] = fc_heap[fc_parent];
		fc_holepos = fc_parent;
	}
	fc_heap[fc_holepos] = fc_blocknum;
}

/*
 * 懒惰地分配和初始化读取缓冲区。这可以避免在同时打开多个
 * 磁带时的浪费，但并不是所有磁带在倒带和读取之间都是
 * 活跃的。
 */
static void fc_ltsInitReadBuffer(LogicalTape *fc_lt)
{
	Assert(fc_lt->buffer_size > 0);
	fc_lt->buffer = palloc(fc_lt->buffer_size);

	/* 读取第一个块，或在磁带为空时重置 */
	fc_lt->nextBlockNumber = fc_lt->firstBlockNumber;
	fc_lt->pos = 0;
	fc_lt->nbytes = 0;
	fc_ltsReadFillBuffer(fc_lt);
}

/*
 * 创建一个磁带集，底层由一个临时文件支持。
 *
 * 磁带集最初是空的。使用 LogicalTapeCreate() 在其中创建
 * 磁带。
 *
 * 在单进程排序中，为文件集传递 NULL 参数，为工作者传递 -1。
 *
 * 在并行排序中，并行工作者传递共享文件集句柄和自己的
 * 工作者编号。在工作者完成后，领导者创建磁带集，传递
 * 共享文件集句柄和 -1 作为工作者，并使用 LogicalTapeImport()
 * 将工作者磁带导入其中。
 *
 * 当前，领导者只能将工作者磁带导入集合，而不创建自己的
 * 磁带，尽管理论上这是可行的。
 *
 * 如果 preallocate 为真，则为每个单独的磁带批量分配块。
 * 这避免了同时写入多个磁带时的碎片化。
 */
LogicalTapeSet *
LogicalTapeSetCreate(bool fc_preallocate, SharedFileSet *fc_fileset, int fc_worker)
{
	LogicalTapeSet *fc_lts;

	/*
	 * 创建包括每个磁带的 LogicalTape 结构的顶层结构。
	 */
	fc_lts = (LogicalTapeSet *) palloc(sizeof(LogicalTapeSet));
	fc_lts->nBlocksAllocated = 0L;
	fc_lts->nBlocksWritten = 0L;
	fc_lts->nHoleBlocks = 0L;
	fc_lts->forgetFreeSpace = false;
	fc_lts->freeBlocksLen = 32;	/* 合理的初始估计 */
	fc_lts->freeBlocks = (long *) palloc(fc_lts->freeBlocksLen * sizeof(long));
	fc_lts->nFreeBlocks = 0;
	fc_lts->enable_prealloc = fc_preallocate;

	fc_lts->fileset = fc_fileset;
	fc_lts->worker = fc_worker;

	/*
	 * 根据需要创建临时 BufFile 存储。
	 *
	 * 在领导者中，我们劫持第一个导入磁带的 BufFile，并
	 * 将任何后续磁带的 BufFile 连接到该 BufFile。因此这里不
	 * 创建 BufFile。对于工作者案例和串行案例来说事情更简单，
	 * 它们通常非常相似——工作者使用共享文件集，而串行排序
	 * 使用常规串行 BufFile。
	 */
	if (fc_fileset && fc_worker == -1)
		fc_lts->pfile = NULL;
	else if (fc_fileset)
	{
		char		fc_filename[MAXPGPATH];

		pg_itoa(fc_worker, fc_filename);
		fc_lts->pfile = BufFileCreateFileSet(&fc_fileset->fs, fc_filename);
	}
	else
		fc_lts->pfile = BufFileCreateTemp(false);

	return fc_lts;
}

/*
 * 从现有共享 BufFile 中声明逻辑磁带的所有权。
 *
 * 调用者应为领导者进程。尽管磁带在工作者中标记为
 * 冻结，但在领导者中打开时并未被冻结，因为未冻结的磁带
 * 使用更大的读取缓冲区。（冻结的磁带具有较小的读取
 * 缓冲区，针对随机访问进行了优化。）
 */
LogicalTape *
LogicalTapeImport(LogicalTapeSet *fc_lts, int fc_worker, TapeShare *fc_shared)
{
	LogicalTape *fc_lt;
	long		fc_tapeblocks;
	char		fc_filename[MAXPGPATH];
	BufFile    *fc_file;
	int64		fc_filesize;

	fc_lt = fc_ltsCreateTape(fc_lts);

	/*
	 * 构建所有 BufFile 的连接视图，记住每个源文件开始的
	 * 块编号。
	 */
	pg_itoa(fc_worker, fc_filename);
	fc_file = BufFileOpenFileSet(&fc_lts->fileset->fs, fc_filename, O_RDONLY, false);
	fc_filesize = BufFileSize(fc_file);

	/*
	 * 首先存储 BufFile，并将后续 BufFiles 连接到该 BufFile。随着
	 * 的进行，将块偏移量存储到每个磁带中。
	 */
	fc_lt->firstBlockNumber = fc_shared->firstblocknumber;
	if (fc_lts->pfile == NULL)
	{
		fc_lts->pfile = fc_file;
		fc_lt->offsetBlockNumber = 0L;
	}
	else
	{
		fc_lt->offsetBlockNumber = BufFileAppend(fc_lts->pfile, fc_file);
	}
	/* 不要为读取缓冲区分配超过实际需要的空间 */
	fc_lt->max_size = Min(MaxAllocSize, fc_filesize);
	fc_tapeblocks = fc_filesize / BLCKSZ;

	/*
	 * 更新已分配块的数量和已写入块的数量，以反映导入的
	 * BufFile。已分配/已写入块包括连接的 BufFiles 之间留下的空隙
	 * 使用的空间。还跟踪空洞块的数量，以便我们可以稍后向后计算
	 * 物理块的数量以进行仪器化。
	 */
	fc_lts->nHoleBlocks += fc_lt->offsetBlockNumber - fc_lts->nBlocksAllocated;

	fc_lts->nBlocksAllocated = fc_lt->offsetBlockNumber + fc_tapeblocks;
	fc_lts->nBlocksWritten = fc_lts->nBlocksAllocated;

	return fc_lt;
}

/*
 * 关闭逻辑磁带集并释放所有资源。
 *
 * 注意：这并不关闭任何磁带！你必须先关闭它们，或者可以让
 * 它们和内存上下文一起被销毁。
 */
void LogicalTapeSetClose(LogicalTapeSet *fc_lts)
{
	BufFileClose(fc_lts->pfile);
	pfree(fc_lts->freeBlocks);
	pfree(fc_lts);
}

/*
 * 在给定的磁带集中创建一个逻辑磁带。
 *
 * 磁带在写入状态下初始化。
 */
LogicalTape *
LogicalTapeCreate(LogicalTapeSet *fc_lts)
{
	/*
	 * 当前唯一阻止在领导者中创建新磁带的原因是通过
	 * BufFileOpenShared() 打开的 BufFiles 定义为只读，
	 * 但如果认为值得，可以改变这一点。目前，写入
	 * 领导者磁带将引发“坏文件描述符”错误，因此
	 * tuplesort 必须完全避免写入领导者磁带。
	 */
	if (fc_lts->fileset && fc_lts->worker == -1)
		elog(ERROR, "cannot create new tapes in leader process");

	return fc_ltsCreateTape(fc_lts);
}

static LogicalTape *
fc_ltsCreateTape(LogicalTapeSet *fc_lts)
{
	LogicalTape *fc_lt;

	/*
	 * 创建每个磁带的结构。请注意，我们懒惰地分配 I/O 缓冲区。
	 */
	fc_lt = palloc(sizeof(LogicalTape));
	fc_lt->tapeSet = fc_lts;
	fc_lt->writing = true;
	fc_lt->frozen = false;
	fc_lt->dirty = false;
	fc_lt->firstBlockNumber = -1L;
	fc_lt->curBlockNumber = -1L;
	fc_lt->nextBlockNumber = -1L;
	fc_lt->offsetBlockNumber = 0L;
	fc_lt->buffer = NULL;
	fc_lt->buffer_size = 0;
	/* palloc() 超过 MaxAllocSize 会失败 */
	fc_lt->max_size = MaxAllocSize;
	fc_lt->pos = 0;
	fc_lt->nbytes = 0;
	fc_lt->prealloc = NULL;
	fc_lt->nprealloc = 0;
	fc_lt->prealloc_size = 0;

	return fc_lt;
}

/*
 * 关闭逻辑磁带。
 *
 * 注意：这不会将任何块返回到空闲列表！你必须先读取
 * 磁带直到结束，才能重用空间。不过，在当前使用中，
 * 我们只在完全读取它们后关闭磁带。
 */
void LogicalTapeClose(LogicalTape *fc_lt)
{
	if (fc_lt->buffer)
		pfree(fc_lt->buffer);
	pfree(fc_lt);
}

/*
 * 将逻辑磁带标记为不再需要管理空闲空间。
 *
 * 如果调用方不打算在磁带集中写入更多数据，但正在从未冻结的
 * 磁带中读取，则应调用此函数。由于不再计划写入，因此记住空闲
 * 块已经不再有用。设置此标志可以避免在 ltsReleaseBlock() 中
 * 浪费时间和空间，后者并没有设计来处理大量空闲块。
 */
void LogicalTapeSetForgetFreeSpace(LogicalTapeSet *fc_lts)
{
	fc_lts->forgetFreeSpace = true;
}

/*
 * 写入逻辑磁带。
 *
 * 没有错误返回；我们在失败时通过 ereport() 报告错误。
 */
void LogicalTapeWrite(LogicalTape *fc_lt, void *fc_ptr, size_t fc_size)
{
	LogicalTapeSet *fc_lts = fc_lt->tapeSet;
	size_t		fc_nthistime;

	Assert(fc_lt->writing);
	Assert(fc_lt->offsetBlockNumber == 0L);

	/* 在第一次写入时分配数据缓冲区和第一个块 */
	if (fc_lt->buffer == NULL)
	{
		fc_lt->buffer = (char *) palloc(BLCKSZ);
		fc_lt->buffer_size = BLCKSZ;
	}
	if (fc_lt->curBlockNumber == -1)
	{
		Assert(fc_lt->firstBlockNumber == -1);
		Assert(fc_lt->pos == 0);

		fc_lt->curBlockNumber = fc_ltsGetBlock(fc_lts, fc_lt);
		fc_lt->firstBlockNumber = fc_lt->curBlockNumber;

		TapeBlockGetTrailer(fc_lt->buffer)->prev = -1L;
	}

	Assert(fc_lt->buffer_size == BLCKSZ);
	while (fc_size > 0)
	{
		if (fc_lt->pos >= (int) TapeBlockPayloadSize)
		{
			/* 缓冲区满了，抛弃它 */
			long		fc_nextBlockNumber;

			if (!fc_lt->dirty)
			{
				/* 嗯，直接从读取跳到写入了？ */
				elog(ERROR, "invalid logtape state: should be dirty");
			}

			/*
			 * 首先分配下一个块，以便我们可以将其存储在此块的
			 * 'next' 指针中。
			 */
			fc_nextBlockNumber = fc_ltsGetBlock(fc_lt->tapeSet, fc_lt);

			/* 设置下一个指针并抛弃当前块。 */
			TapeBlockGetTrailer(fc_lt->buffer)->next = fc_nextBlockNumber;
			fc_ltsWriteBlock(fc_lt->tapeSet, fc_lt->curBlockNumber, (void *) fc_lt->buffer);

			/* 初始化下一个块的前指针 */
			TapeBlockGetTrailer(fc_lt->buffer)->prev = fc_lt->curBlockNumber;
			fc_lt->curBlockNumber = fc_nextBlockNumber;
			fc_lt->pos = 0;
			fc_lt->nbytes = 0;
		}

		fc_nthistime = TapeBlockPayloadSize - fc_lt->pos;
		if (fc_nthistime > fc_size)
			fc_nthistime = fc_size;
		Assert(fc_nthistime > 0);

		memcpy(fc_lt->buffer + fc_lt->pos, fc_ptr, fc_nthistime);

		fc_lt->dirty = true;
		fc_lt->pos += fc_nthistime;
		if (fc_lt->nbytes < fc_lt->pos)
			fc_lt->nbytes = fc_lt->pos;
		fc_ptr = (void *) ((char *) fc_ptr + fc_nthistime);
		fc_size -= fc_nthistime;
	}
}

/*
 * 回退逻辑磁带并从写入模式切换到读取模式。
 *
 * 磁带当前必须处于写入状态，或者在读取状态下“冻结”。
 *
 * 'buffer_size' 指定用于读取缓冲区的内存量。
 * 无论传入参数如何，实际使用的内存量在 BLCKSZ 和 MaxAllocSize 之间，并且是 BLCKSZ 的倍数。如果必要，给定的值将向下舍入并截断以符合这些约束。如果磁带被冻结，则忽略 'buffer_size' 参数，并使用一个小的 BLCKSZ 字节缓冲区。
 */
void LogicalTapeRewindForRead(LogicalTape *fc_lt, size_t fc_buffer_size)
{
	LogicalTapeSet *fc_lts = fc_lt->tapeSet;

	/*
	 * 如果需要，对 buffer_size 进行四舍五入和限制。
	 */
	if (fc_lt->frozen)
		fc_buffer_size = BLCKSZ;
	else
	{
		/* 至少需要一个块 */
		if (fc_buffer_size < BLCKSZ)
			fc_buffer_size = BLCKSZ;

		/* palloc() 大于 max_size 的可能性不大，有帮助 */
		if (fc_buffer_size > fc_lt->max_size)
			fc_buffer_size = fc_lt->max_size;

		/* 向下舍入到 BLCKSZ 边界 */
		fc_buffer_size -= fc_buffer_size % BLCKSZ;
	}

	if (fc_lt->writing)
	{
		/*
		 * 完成写入阶段。刷新最后一个部分数据块，并
		 * 回退以进行正常（破坏性）读取。
		 */
		if (fc_lt->dirty)
		{
			/*
			 * 只要我们至少填充过一次缓冲区，从 valgrind 的角度来看，其内容是完全定义的，即使当前端点之外的内容可能是过时的。但在并行排序的情况下，有可能对如此少量数据进行排序，以至于我们甚至一次都没有填满缓冲区。告知 valgrind 其内容已定义，以便它不会发出警告。
			 */
			VALGRIND_MAKE_MEM_DEFINED(lt->buffer + lt->nbytes,
									  lt->buffer_size - lt->nbytes);

			TapeBlockSetNBytes(fc_lt->buffer, fc_lt->nbytes);
			fc_ltsWriteBlock(fc_lt->tapeSet, fc_lt->curBlockNumber, (void *) fc_lt->buffer);
		}
		fc_lt->writing = false;
	}
	else
	{
		/*
		 * 只有在磁带被冻结的情况下才可以这样做；我们回退进行（另一个）读取。
		 */
		Assert(fc_lt->frozen);
	}

	if (fc_lt->buffer)
		pfree(fc_lt->buffer);

	/* 缓冲区是延迟分配的，但在这里设置大小 */
	fc_lt->buffer = NULL;
	fc_lt->buffer_size = fc_buffer_size;

	/* 释放预分配列表，并返回未使用的块编号 */
	if (fc_lt->prealloc != NULL)
	{
		for (int fc_i = fc_lt->nprealloc; fc_i > 0; fc_i--)
			fc_ltsReleaseBlock(fc_lts, fc_lt->prealloc[fc_i - 1]);
		pfree(fc_lt->prealloc);
		fc_lt->prealloc = NULL;
		fc_lt->nprealloc = 0;
		fc_lt->prealloc_size = 0;
	}
}

/*
 * 从逻辑磁带读取。
 *
 * 提前到达文件末尾（EOF）由返回值小于请求字节数表示。
 */
size_t LogicalTapeRead(LogicalTape *fc_lt, void *fc_ptr, size_t fc_size)
{
	size_t		fc_nread = 0;
	size_t		fc_nthistime;

	Assert(!fc_lt->writing);

	if (fc_lt->buffer == NULL)
		fc_ltsInitReadBuffer(fc_lt);

	while (fc_size > 0)
	{
		if (fc_lt->pos >= fc_lt->nbytes)
		{
			/* 尝试将更多数据加载到缓冲区。 */
			if (!fc_ltsReadFillBuffer(fc_lt))
				break;			/* EOF */
		}

		fc_nthistime = fc_lt->nbytes - fc_lt->pos;
		if (fc_nthistime > fc_size)
			fc_nthistime = fc_size;
		Assert(fc_nthistime > 0);

		memcpy(fc_ptr, fc_lt->buffer + fc_lt->pos, fc_nthistime);

		fc_lt->pos += fc_nthistime;
		fc_ptr = (void *) ((char *) fc_ptr + fc_nthistime);
		fc_size -= fc_nthistime;
		fc_nread += fc_nthistime;
	}

	return fc_nread;
}

/*
 * “冻结”磁带的内容，以便可以多次读取和/或向后读取。一旦磁带被冻结，其内容在 LogicalTapeSet 被销毁之前不会释放。这预计仅在合并的最终输出阶段使用。
 *
 * 此操作 *必须* 在写入阶段结束时调用，在磁带回退之前（回退后太晚了！）。它会“免费”执行回退并切换到读取模式。紧接着的读取模式回退调用是可以的，但不是必要的。
 *
 * share 输出参数设置用于冻结后磁带的存储详细信息，这可能会在稍后传递给领导进程中的 LogicalTapeSetCreate。此元数据仅对冻结最终输出以供领导使用的工作调用者感兴趣（单个物化磁带）。串行排序应将 share 设置为 NULL。
 */
void LogicalTapeFreeze(LogicalTape *fc_lt, TapeShare *fc_share)
{
	LogicalTapeSet *fc_lts = fc_lt->tapeSet;

	Assert(fc_lt->writing);
	Assert(fc_lt->offsetBlockNumber == 0L);

	/*
	 * 完成写入阶段。刷新最后一个部分数据块，并回退
	 * 以进行非破坏性读取。
	 */
	if (fc_lt->dirty)
	{
		/*
		 * 只要我们至少填充了缓冲区一次，从 valgrind 的角度来看，
		 * 其内容就完全定义了，即使当前结束点之后的内容可能是过时的。
		 * 但在并行排序的情况下，处理如此少量的数据可能不会让我们
		 * 甚至填充缓冲区一次。告诉 valgrind 其内容是定义的，以便它
		 * 不会发出警告。
		 */
		VALGRIND_MAKE_MEM_DEFINED(lt->buffer + lt->nbytes,
								  lt->buffer_size - lt->nbytes);

		TapeBlockSetNBytes(fc_lt->buffer, fc_lt->nbytes);
		fc_ltsWriteBlock(fc_lt->tapeSet, fc_lt->curBlockNumber, (void *) fc_lt->buffer);
	}
	fc_lt->writing = false;
	fc_lt->frozen = true;

	/*
	 * seek 和 backspace 函数假定使用单个块读取缓冲区。
	 * 这在当前使用中是可以的。更大的缓冲区有助于使后备文件的
	 * 读取模式对操作系统看起来更顺序，当我们从多个磁带读取时。
	 * 但在排序结束时，当磁带被冻结时，我们无论如何只会从单个磁带读取。
	 */
	if (!fc_lt->buffer || fc_lt->buffer_size != BLCKSZ)
	{
		if (fc_lt->buffer)
			pfree(fc_lt->buffer);
		fc_lt->buffer = palloc(BLCKSZ);
		fc_lt->buffer_size = BLCKSZ;
	}

	/* 读取第一个块，或在磁带为空时重置 */
	fc_lt->curBlockNumber = fc_lt->firstBlockNumber;
	fc_lt->pos = 0;
	fc_lt->nbytes = 0;

	if (fc_lt->firstBlockNumber == -1L)
		fc_lt->nextBlockNumber = -1L;
	fc_ltsReadBlock(fc_lt->tapeSet, fc_lt->curBlockNumber, (void *) fc_lt->buffer);
	if (TapeBlockIsLast(fc_lt->buffer))
		fc_lt->nextBlockNumber = -1L;
	else
		fc_lt->nextBlockNumber = TapeBlockGetTrailer(fc_lt->buffer)->next;
	fc_lt->nbytes = TapeBlockGetNBytes(fc_lt->buffer);

	/* 当调用者要共享其磁带集时处理额外步骤 */
	if (fc_share)
	{
		BufFileExportFileSet(fc_lts->pfile);
		fc_share->firstblocknumber = fc_lt->firstBlockNumber;
	}
}

/*
 * 将磁带向后移动指定的字节数。  (我们还支持更通用的
 * seek 接口，见下文。)
 *
 * *只有* 被冻结以供读取的磁带可以被倒退；我们不支持
 * 在写入期间的随机访问，未冻结的读取磁带可能已经
 * 丢弃了所需的数据！
 *
 * 返回备份的字节数。如果在当前
 * 位置之前没有那么多数据，它可能会少于请求的数量。
 * 在这种情况下，磁带被定位到磁带的开始。
 */
size_t LogicalTapeBackspace(LogicalTape *fc_lt, size_t fc_size)
{
	size_t		fc_seekpos = 0;

	Assert(fc_lt->frozen);
	Assert(fc_lt->buffer_size == BLCKSZ);

	if (fc_lt->buffer == NULL)
		fc_ltsInitReadBuffer(fc_lt);

	/*
	 * 在当前块内的简单情况。
	 */
	if (fc_size <= (size_t) fc_lt->pos)
	{
		fc_lt->pos -= (int) fc_size;
		return fc_size;
	}

	/*
	 * 难度不小，必须回溯块链。这个实现对于长时间的 seek 来说
	 * 效率相当低，但我们实际上并不这样做（对一个元组的 seek 是典型的）。
	 */
	fc_seekpos = (size_t) fc_lt->pos; /* 此块内的部分 */
	while (fc_size > fc_seekpos)
	{
		long		fc_prev = TapeBlockGetTrailer(fc_lt->buffer)->prev;

		if (fc_prev == -1L)
		{
			/* 尝试向后移动超出磁带的开始。 */
			if (fc_lt->curBlockNumber != fc_lt->firstBlockNumber)
				elog(ERROR, "unexpected end of tape");
			fc_lt->pos = 0;
			return fc_seekpos;
		}

		fc_ltsReadBlock(fc_lt->tapeSet, fc_prev, (void *) fc_lt->buffer);

		if (TapeBlockGetTrailer(fc_lt->buffer)->next != fc_lt->curBlockNumber)
			elog(ERROR, "broken tape, next of block %ld is %ld, expected %ld",
				 fc_prev,
				 TapeBlockGetTrailer(fc_lt->buffer)->next,
				 fc_lt->curBlockNumber);

		fc_lt->nbytes = TapeBlockPayloadSize;
		fc_lt->curBlockNumber = fc_prev;
		fc_lt->nextBlockNumber = TapeBlockGetTrailer(fc_lt->buffer)->next;

		fc_seekpos += TapeBlockPayloadSize;
	}

	/*
	 * 'seekpos' 现在可以大于 'size'，因为它指向目标块的
	 * 开始。两者之间的差异是页面内的位置。
	 */
	fc_lt->pos = fc_seekpos - fc_size;
	return fc_size;
}

/*
 * 在逻辑磁带中的任意位置进行 seek。
 *
 * *只有* 被冻结以供读取的磁带可以进行 seek。
 *
 * 必须使用先前由 LogicalTapeTell() 返回的块/偏移量调用。
 */
void LogicalTapeSeek(LogicalTape *fc_lt, long fc_blocknum, int fc_offset)
{
	Assert(fc_lt->frozen);
	Assert(fc_offset >= 0 && fc_offset <= TapeBlockPayloadSize);
	Assert(fc_lt->buffer_size == BLCKSZ);

	if (fc_lt->buffer == NULL)
		fc_ltsInitReadBuffer(fc_lt);

	if (fc_blocknum != fc_lt->curBlockNumber)
	{
		fc_ltsReadBlock(fc_lt->tapeSet, fc_blocknum, (void *) fc_lt->buffer);
		fc_lt->curBlockNumber = fc_blocknum;
		fc_lt->nbytes = TapeBlockPayloadSize;
		fc_lt->nextBlockNumber = TapeBlockGetTrailer(fc_lt->buffer)->next;
	}

	if (fc_offset > fc_lt->nbytes)
		elog(ERROR, "invalid tape seek position");
	fc_lt->pos = fc_offset;
}

/*
 * 以适合稍后 LogicalTapeSeek 的形式获取当前位置信息。
 *
 * 注意：在写入阶段执行此操作，并打算在冻结后使用此位置进行 seek 是可以的。
 * 不清楚是否有任何人需要这个。
 */
void LogicalTapeTell(LogicalTape *fc_lt, long *fc_blocknum, int *fc_offset)
{
	if (fc_lt->buffer == NULL)
		fc_ltsInitReadBuffer(fc_lt);

	Assert(fc_lt->offsetBlockNumber == 0L);

	/* 在更大的缓冲区中，'pos' 不会与页面内的偏移量相同 */
	Assert(fc_lt->buffer_size == BLCKSZ);

	*fc_blocknum = fc_lt->curBlockNumber;
	*fc_offset = fc_lt->pos;
}

/*
 * 获取当前由 LogicalTapeSet 使用的总磁盘空间，以块为单位。
 * 不计算打开的写缓冲区（如有）。
 */
long LogicalTapeSetBlocks(LogicalTapeSet *fc_lts)
{
	return fc_lts->nBlocksWritten - fc_lts->nHoleBlocks;
}
